package com.wangsd.common.utils.weight;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * Created by xc on 2019/11/25
 * 代码清单7-9　带权重的选择WeightRandom
 */
public class WeightRandom {
    private Pair[] options;
    private double[] cumulativeProbabilities;
    private Random rnd;

    public WeightRandom(Pair[] options) {
        this.options = options;
        this.rnd = new Random();
        prepare();
    }

    /**
     * prepare()方法计算每个选项的累计概率，保存在数组cumulativeProbabilities中
     */
    private void prepare() {
        int weights = 0;
        for (Pair pair : options) {
            weights += pair.getWeight();
        }
        cumulativeProbabilities = new double[options.length];
        int sum = 0;
        for (int i = 0; i < options.length; i++) {
            sum += options[i].getWeight();
            cumulativeProbabilities[i] = sum / (double) weights;
        }
    }

    /**
     * nextItem()方法根据权重随机选择一个，具体就是，首先生成一个0～1的数，
     * 然后使用二分查找，如果没找到，返回结果是-（插入点）-1，所以-index-1就是插入点，插入点的位置就对应选项的索引。
     *
     * @return
     */
    public Object nextItem() {
        double randomValue = rnd.nextDouble();
        int index = Arrays.binarySearch(cumulativeProbabilities, randomValue);
        if (index < 0) {
            index = -index - 1;
        }
        return options[index].getItem();
    }


    public static void main(String[] args) {
        Pair p1 = new Pair("1", 10000);
        Pair p2 = new Pair("2", 5);
        Pair p3 = new Pair("3", 500);
        List list = new ArrayList<Pair>();
        list.add(p1);
        list.add(p2);
        list.add(p3);
        Pair[] options = new Pair[list.size()];
        list.toArray(options);
//        Pair[] options = new Pair[]{new Pair("1", 5), new Pair("2", 20), new Pair("3", 75)};
        WeightRandom rnd = new WeightRandom(options);
        int a = 0, b = 0, c = 0;
        for (int i = 0; i < 5000; i++) {
            if (rnd.nextItem().equals("2")) {
                b++;
            }else if (rnd.nextItem().equals("3")) {
                c++;
            } else {
                a++;
            }
        }
        System.out.println("a=" + a);
        System.out.println("b=" + b);
        System.out.println("c=" + c);

    }
}